package leetcode.剑指offer.剑指II;

import leetcode.util.CommonUtils;
import leetcode.剑指offer.pojo.ListNode;
import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author ：zsy
 * @date ：Created 2022/10/14 5:14 PM
 * @description：
 */
public class 剑指_II_078_合并排序链表 {
    @Test
    public void test() {
        int[][] nums = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        // int[][] nums = {{}};
        ListNode[] lists = new ListNode[nums.length];
        for (int i = 0; i < nums.length; i++) {
            lists[i] = CommonUtils.transferArrToListNode(nums[i]);
            CommonUtils.printListNode(lists[i]);
        }
        Solution solution = new Solution();
        ListNode head = solution.mergeKLists(lists);
        CommonUtils.printListNode(head);
    }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            ListNode head = new ListNode(-1);
            ListNode tmp = head;
            PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
            for (ListNode list : lists) {
                if (list != null) {
                    queue.offer(list);
                }
            }
            while (!queue.isEmpty()) {
                ListNode node = queue.poll();
                tmp.next = node;
                tmp = tmp.next;
                if (node.next != null) {
                    queue.offer(node.next);
                }
            }
            return head.next;
        }
    }
}
